#include "myGraph.h"
#include <iostream>
#include <sstream>
#include <string>
#include <queue>

using namespace std;

EdgeNode::EdgeNode()
{
    this->dest = 0;
    this->link = nullptr;
}

EdgeNode::EdgeNode(int dest, EdgeNode *link)
{
    this->dest = dest;
    this->link = link;
}

EdgeNode::~EdgeNode()
{
}

int EdgeNode::getDest()
{
    return dest;
}

EdgeNode *EdgeNode::getNext()
{
    return link;
}

void EdgeNode::setDest(int dest)
{
    this->dest = dest;
}

void EdgeNode::setNext(EdgeNode *link)
{
    this->link = link;
}

VertexNode::VertexNode()
{
    this->data = '\0';
    this->firstEdge = nullptr;
}

VertexNode::VertexNode(char data, EdgeNode *firstEdge)
{
    this->data = data;
    this->firstEdge = firstEdge;
}

VertexNode::~VertexNode()
{
}

char VertexNode::getData()
{
    return data;
}

EdgeNode *VertexNode::getFirstEdge()
{
    return firstEdge;
}

void VertexNode::setData(char data)
{
    this->data = data;
}

void VertexNode::setFirstEdge(EdgeNode *firstEdge)
{
    this->firstEdge = firstEdge;
}

MyGraph::MyGraph()
{
    this->nodeNum = 0;
    this->edgeNum = 0;
    this->VexList = nullptr;
}

MyGraph::MyGraph(int nodeNum, int edgeNum, char *nodeList, int *edgeStartList, int *edgeEndList)
{
    this->nodeNum = nodeNum;
    this->edgeNum = edgeNum;
    this->VexList = new VertexNode[nodeNum];
    for (int i = 0; i < nodeNum; i++)
    {
        this->VexList[i].setData(nodeList[i]);
    }
    for (int i = 0; i < edgeNum; i++)
    {
        int start = edgeStartList[i];
        int end = edgeEndList[i];

        EdgeNode *edge = new EdgeNode(end, this->VexList[start].getFirstEdge());
        this->VexList[start].setFirstEdge(edge);

        EdgeNode *edge1 = new EdgeNode(start, this->VexList[end].getFirstEdge());
        this->VexList[end].setFirstEdge(edge1);
    }
}

MyGraph::~MyGraph()
{
}

int MyGraph::getNodeNum()
{
    return nodeNum;
}

int MyGraph::getEdgeNum()
{
    return edgeNum;
}

string MyGraph::printGraph()
{
    string result = "";
    for (int i = 0; i < nodeNum; i++)
    {

        result += (VexList[i].getData());
        result += ":";

        EdgeNode *edge = VexList[i].getFirstEdge();
        while (edge != nullptr)
        {
            result += " ";
            result += (VexList[edge->getDest()].getData());

            edge = edge->getNext();
        }
        if (i != nodeNum - 1)
        {
            result += "\n";
        }
    }

    return result;
}

int MyGraph::getFirstNeighbor(int v, int *visited)
{
    return 0;
}

int MyGraph::getNextNeighbor(int v, int w, int *visited)
{
    return 0;
}

void MyGraph::DFS(int v, int *visited, string &result)
{
    visited[v] = 1;
    EdgeNode *edge;
    result += this->VexList[v].getData();
    result += " ";
    edge = this->VexList[v].getFirstEdge();
    while (edge != nullptr)
    {
        if (visited[edge->getDest()] == 0)
        {
            DFS(edge->getDest(), visited, result);
        }
        edge = edge->getNext();
    }
}

string MyGraph::graph_DFS_Traverse()
{
    int n = this->nodeNum;
    int *visited = new int[n];
    string result = "";
    for (int i = 0; i < n; i++)
    {
        visited[i] = 0;
    }
    for (int i = 0; i < n; i++)
    {
        if (visited[i] == 0)
        {
            DFS(i, visited, result);
        }
    }

    return result;
}

void MyGraph::BFS(int v, int *visited, string &result)
{
}

string MyGraph::graph_BFS_Traverse()
{
    int n = this->nodeNum;
    int *visited = new int[n];
    string result = "";
    EdgeNode *p;
    for (int i = 0; i < n; i++)
    {
        visited[i] = 0;
    }
    queue<int> q;
    for (int i = 0; i < n; i++)
    {
        if (visited[i] == 0)
        {
            visited[i] = 1;
            result += this->VexList[i].getData();
            result += " ";
            q.push(i);

            while (!q.empty())
            {
                i = q.front();
                q.pop();
                p = this->VexList[i].getFirstEdge();
                while (p != nullptr)
                {
                    if (visited[p->getDest()] == 0)
                    {
                        visited[p->getDest()] = 1;
                        result += this->VexList[p->getDest()].getData();
                        result += " ";
                        q.push(p->getDest());
                    }
                    p = p->getNext();
                }
            }
        }
    }

    return result;
}
